#include "Heap sort.h"

// 堆排序,并不是在排序过程中使用了堆这一种数据结构,而是使用了堆的算法思想
// 因为堆这种数据结构的特点,堆顶永远是极值
// 就是说: 我们每次将堆顶的值和最后的交换,然后数据长度减1,再进行向下排序,就可以保证排出一个有序的数组来了
// 堆排序的时间复杂度为: O(nlogn)

// 交换函数

void Swap (HPDataType* x , HPDataType* y)
{

    HPDataType tmp = *x ;

    *x = *y ;

    *y = tmp ;

}

// 向上调整算法

void AdjustUp (HPDataType* arr , int child)
{

    int parent = (child - 1) / 2 ;

    while (child > 0)
    {
        
        // 建大堆 >
        // 建小堆 <

        if (arr [child] > arr [parent])
        {

            Swap (&arr [child] , &arr [parent]) ;

            child = parent ;

            parent = (child - 1) / 2 ;

        }

        else
        {

            break ;

        }

    }
    
}

// 向下调整算法

void AdjustDown (HPDataType* arr , int parent , int n)
{

    int child = parent * 2 + 1 ; // 左孩子

    while (child < n)
    {

        // 建大堆 <
        // 建小堆 >

        if (child + 1 < n && arr [child] < arr [child + 1])
        {

            child++ ;

        }

        // 建大堆 <
        // 建小堆 >

        if (arr [parent] < arr [child])
        {

            Swap (&arr [child] , &arr [parent]) ;
            
            parent = child ;

            child = parent * 2 + 1 ;

        }

        else
        {

            break ;

        }

    }
    
}

// 堆排序函数
// 由于不能使用堆这个数据结构,只用了堆的思想
// 所以我们在处理数组的时候,需要把数组变成类似堆的结构,才能进行比较

// 怎么变成把一坨数组变成堆呢？有两种方法:
// (1).从根节点开始,从上往下地将每一个节点向上调整,直到把数组调整成类似堆结构,树的根节点为极值
// (2).从最小子树开始,从其根节点往下向下调整,最小子树有序了就可以往上调整,最后整个数组结构就会变成堆结构

// 但是,我们实际进行堆排序的时候,对数组变成堆结构的处理一般都是使用向下调整算法
// 因为向下调整算法的时间复杂度低于向上调整算法
// 向下调整: O(n)
// 向上调整: O(nlogn)

void HeapSort (HPDataType* arr , int n)
{

    // 建堆---向上调整算法建堆
    
    // for (int i = 0 ; i < n ; i++)
    // {

    //     AdjustUp (arr , i) ;

    // }

    // 建堆---向下调整算法建堆

    for (int i = (n - 1 - 1) / 2 ; i >= 0 ; i--) // n - 1才为叶子节点的下标,要查找父节点的下标要再减1再除
    {

        AdjustDown (arr , i , n) ;

    }

    // 堆排序: O(nlogn)

    int end = n - 1 ;

    while (end > 0)
    {

        Swap (&arr [0] , &arr [end]) ; // 将极值移到数组最后面

        AdjustDown (arr , 0 , end) ; // 再使用向下调整找极值

        end-- ; // 忽略已经排序好的元素

    }

}